class MapSum {
public:
    unordered_map<char,MapSum*> next;
    int value;
    bool isEnd;
    /** Initialize your data structure here. */
    MapSum() {
        value = 0;
        isEnd = false;
    }
    
    void insert(string key, int val) {
        MapSum* cur = this;
        for(char c : key){
            if(!cur->next.count(c)){
                cur->next[c] = new MapSum();
            }
            cur = cur->next[c];
        }
        cur->isEnd = true;
        cur->value = val;
    }
    
    int dfs(MapSum* cur){
        int ret = 0;
        ret += cur->value;
        for(auto& [c,M] : cur->next){
            ret += dfs(M);
        }
        
        return ret;
    }
                                        
    int sum(string prefix) {
        MapSum* cur = this;
        for(char c : prefix){
            if(!cur->next.count(c)){
                return 0;
            }
            cur = cur->next[c];
        }
        
        return dfs(cur);
    }
};
